This application incorporates by reference Taiwanese application Serial No. 88121613, filed on Dec. 9, 1999.
1. Field of the Invention
The invention relates in general to a memory mapping method and more particularly to a memory mapping method for mapping a data array into a memory.
2. Description of the Related Art
As the computer sciences improve, people demand more from modern devices. The processing rate performed by the computer also increases faster and faster. Therefore, people demand more from recording media such as digital versatile disk (DVD), floppy disk, compact disk (CD), hard disk . . . etc. The DVD, with its high storage capacity, is expected to be the focus of the future.
In the personal computer (PC), the data stored in the DVD is read out and decoded by the DVD-ROM (read only memory) player. The decoded data is then received and processed by a host machine, for example, a personal computer. FIG. 1 shows a block diagram for the conventional DVD-ROM player. As shown in FIG. 1, an optical reading head 102 reads data from a DVD 101. The optical reading head 102 is a mechanically operated optical device. The output from the optical reading head 102, in analog form, is received by a radio frequency (RF) amplifier 103. The output from the RF amplifier 103 is then received by an ESM (Eight to Sixteen Modulation) demodulator 104. The ESM demodulator 104 receives the output from the RF amplifier 103, and performs an ESM demodulation on the received data. The ESM demodulator 104 then writes the demodulated data into a DRAM (Dynamic Random Access Memory) 105 which uses an ECC (Error Correction Code) block as a storage unit. Accordingly, the DRAM 105 includes a number of ECC blocks.
The data structure for the ECC block is shown as FIG. 2A. An ECC block, considered as a data array, is defined as 208 rows by 182 columns. The rows from top to bottom are respectively defined as row 0, row 1, . . . row 192, . . . and row 207. The columns from left to right are respectively defined as column 0, column 1, . . . column 172, . . . column 181. In the ECC block the storage unit is a byte and xe2x80x9cBm,nxe2x80x9d represents data stored in the junction of the m-th row and n-th column. The outer-code parity (PO) data is stored in the last 16 rows, i.e., rows 192xcx9c207. Accordingly, the last 16 rows are defined as PO rows while rows 0xcx9c91 are defined as the data rows. The inner-code parity (PI) data is stored in the last 10 columns, i.e., columns 172xcx9c181, and are defined as PI columns.
The sequence in writing the demodulated data into the ECC block is row 0, row (1, . . . row 11, row 192), (row 12, . . . row 22, row 193), row 24, . . . row 34, row 194, etc. To sum up, the writing steps are: (a) sequentially writing data into adjacent 11 rows of the data row; (b) writing data into one row of the PO row; and (c) repeating (a) and (b) until all data are completely written.
An ECC unit 106 then reads out data from the related ECC block of the DRAM 105 and performs an ECC decoding on the data from the ECC block. ECC decoding is a well-known technique to those who are skilled in the art, therefore the details thereof are not repeated again. The ECC unit 106 reads data twice from the ECC block. The ECC unit 106 first reads data in row direction (PI direction) of the ECC block followed by the column direction (PO direction). In row direction, the reading is performed sequentially from row 0 to row 207. The ECC unit 106 performs ECC by the PI bytes of these rows. In column direction, the reading is performed sequentially from column 0 to column 181. The ECC unit 106 performs ECC by the PO bytes of these columns. If errors are detected during the ECC operation by the ECC unit 106, the ECC unit 106 corrects the errors and writes the corrected data into the related ECC block. Since the ECC unit 106 reads data from and writes data into the DRAM 105, there is signal handshake between the ECC unit 106 and the DRAM 105.
If the ECC unit 106 does not find any error in both row and column directions, an EDC (Error Detection Code) unit 107 does not need to perform error detection on the data. If any erroneous data is found, the ECC unit 106 performs an error-correction operation on the error. Once the ECC unit 106 corrects the erroneous data, the EDC unit 107 reads the related data from the DRAM 105 for EDC check. However, during the EDC check, the PO bytes are not needed and so the EDC unit 107 does not read rows 192xcx9c207 of the related ECC block from the DRAM 105. In other words, the reading sequence is row 0xcx9c191 during the EDC check. Since the EDC reads data from the DRAM 105, there is signal handshake between the EDC unit 107 and the DRAM 105.
After the EDC unit 107 performs the EDC check, the output from the EDC unit 107 is received by an ATAPI (AT Attachment Packet Interface) 108 which then transmits the data into a PC 109. This completes the data transfer from the DVD 101 to the PC 109. If the ESM demodulator 104 writes data into the DRAM 105 in linear address mapping, the result is shown as FIG. 2B. In FIG. 2B, numbers below each byte represent the address for the related byte. For example, the address for B0,0 is 0, and the address for B1,0 is 96. In DRAM 105, a storage unit for an address is a word, and a word consists of two bytes. In FIG. 2B, there are two bytes stored in one address. For example, B0,0, and B0,1, are both stored in address 0. The addresses are arranged from left to right, and from top to bottom. The last ten bytes in each column, marked by xe2x80x9cXxe2x80x9d, represent the dummy data. The dummy data is used to facilitate the accessing speed. Of course, these dummy data are ignored properly, and the data needed is not affected.
The advantage of the linear address mapping is one of easy implementation. However, linear address mapping is only useful in the access of one-dimensional data or in the single direction access of the two-dimensional data arrays. The single direction access means that the access direction is either row direction or column direction. When two-dimensional data arrays need to be accessed in two directions (both row direction and column direction), the performance of the linear address mapping is less then ideal in terms of efficienty.
When linear address mapping is used in two-directional access of two-dimensional data arrays, it often results in a number of pages missing. In a memory, the number of addresses in one page is fixed, for example, 512. When data accessed at the same time are not at the same page, page missing occurs. Page missing reduces the efficiency of data access.
The ECC block in FIG. 2B is taken for example. It is supposed that ECC unit 106 accesses 8 words (16 bytes) from the DRAM 105 at one time. As stated above, the ECC unit 106 reads data twice from the ECC block, one in row direction and the other in column direction. When the ECC unit 106 reads data in row direction, the data read by the ECC unit are always at the same page. In other words, no page missing occurs in row direction access. However, when the ECC unit 106 reads data in column direction, the data read by the ECC unit are not at the same page. In other words, page missing occurs during column direction access.
The data accessed in the first time of column direction access includes (B0,0, B0,1), (B1,0, B1,1), (B2,0, B2,1), (B3,0, B3,1), (B4,0, B4,1), (B5,0, B5,1), (B6,0, B6,1) and (B7,0, B7,1). Referring to FIG. 2B, in column direction access, eight bytes in each of two adjacent columns are accessed at the same time. As shown in FIG. 2B, the addresses for the first six pairs of bytes are limited within 0xcx9c511 while the addresses for (B6,0, B6,1) and (B7,0, B7,1) are limited within 512xcx9c1023. In other words, the first six pairs of bytes are on the same page while the last two pairs of bytes are not on the same page as the first six pairs of bytes. Thus, page missing occurs during first time access in the column direction. Similarly, it is known that one page missing occurs during each access in the column direction. When page missing occurs, the access period becomes longer, resulting in reduced access efficiency.
The second disadvantage of the linear address mapping relates to increased hardware cost. When the linear address mapping is applied in two-directional access, page missing occurs randomly. Therefore, extra circuitry for detecting page missing is required which translates to increased hardware cost.
It is therefore an object of the invention to provide an improved and simplified method of memory mapping used in two-directional access. By the invention, page missing is prevented in two-directional access, resulting in increasing the access rate. In addition, the circuit complexity is reduced.
The invention achieves the above-identified objects by providing a new memory mapping method for two-directional access in two-dimensional data array. The memory mapping method maps a first data array into a second data array for storing into a memory. The first data array contains m rows by n columns. The memory mapping method includes the steps of: (a) dividing each row of the first data array equally into k basic units, wherein n/k is a multiple of 2j, and each basic unit includes n/k bytes; (b) arranging adjacent j basic units in each column of the first data array into a basic memory block in a row manner, wherein each basic memory block includes n*j/k bytes; and (c) arranging the basic memory block in the form of the second data array for storing in the memory; wherein j is the number of words in each row-directional access and column-directional access.
Further, a data structure to store ECC (error correction code) blocks in a memory is provided by the invention. Each ECC block includes access data, outer-code parity (PO) data, and inner-code parity (PI) data. In addition, each ECC block is divided into a PO unit containing the PO data and a number of ESM (eight-to-sixteen modulation) units containing the access data and the PI data. The data structure includes a storage section, which includes PO units of each ECC block. The data structure further includes another storage section, which includes ESM units of each ECC block and a pointer table, which includes a number of pointers that point to the related address of the PO units and the ESM units in the memory.
Still further, the invention provides a memory mapping method for two-directional access in two-dimensional data array. The memory mapping method maps the first data array into the second data array to store into a memory. The first data array includes m rows by n columns. The first data array is obtained by adding a number of dummy data into each row of an ECC (error correction code) block. The memory mapping method includes the following steps. Firstly, each row of the first data array is divided equally into k basic units, wherein n/k is a multiplier multiple of 2j, and each basic unit includes n/k bytes. Secondly, adjacent j basic units in each column of the first data array are arranged into a basic memory block in a row manner, wherein each basic memory block contains n*j/k bytes. Next the basic memory block in the form of the second data array are arranged to store in the memory; wherein j is the number of words in each row-directional access and column-directional access.